#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    int retlen = 1;
    int retcount = 1;

    vector<int> count(n + 10, 1);
    vector<int> len(n + 10, 1);

    for (int i = 2; i <= n; ++i)
    {
        for (int j = i - 1; j >= 1; --j)
        {
            if (nums[i - 1] > nums[j - 1])
            {
                if (len[j] + 1 > len[i])
                {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                }
                else if (len[j] + 1 == len[i])
                {
                    count[i] += count[j];
                }
            }
        }

        if (retlen == len[i])
        {
            retcount += count[i];
        }
        else if (retlen < len[i])
        {
            retlen = len[i];
            retcount = count[i];
        }
    }

    return retcount;
}

int findLongestChain(vector<vector<int>>& pairs) {
    sort(pairs.begin(), pairs.end());

    int n = pairs.size();
    vector<int> dp(n + 10, 1);
    int ret = 1;

    for (int i = 2; i <= n; ++i)
    {
        for (int j = i - 1; j >= 1; --j)
        {
            if (pairs[j - 1][1] < pairs[i - 1][0])
            {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ret = max(dp[i], ret);
    }

    return ret;
}

int main()
{
    findNumberOfLIS({ 1,3,5,4,7 });
	return 0;
}